public class question_45 {
}
//我想采用暴力的dfs直接递归加剪枝
/*
* 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
* */
class Solution_45 {
    public int min_step;
    public void dfs(int[] nums, int index, int step){
//        说明是死路
        if(nums[index]==0){
            return ;
        }
        if(step+1>=min_step){
            return ;
        }
//        这一步是关键
        step=step+1;
        if((index+nums[index])>=nums.length-1){
            min_step=step;
            return;
        }
//      说明还需要吧1到nums[index]之间的每一步都试一下
//        这里我从最大的开始
        for (int i = nums[index]; i >=1; i--) {
            dfs(nums,index+i,step);
        }
    }
    public int jump(int[] nums) {
        if (nums.length==1){
            return 0;
        }
        min_step=Integer.MAX_VALUE;
        dfs(nums,0,0);
        return min_step;
    }
}